/*
 * @lc app=leetcode.cn id=2115 lang=cpp
 *
 * [2115] 从给定原材料中找到所有可以做出的菜
 */

// @lc code=start
class Solution
{
public:
    void updateGraph(string x, unordered_map<string, int> &indeg, unordered_map<string, unordered_set<string>> &graph)
    {
        for (auto x : graph[x])
        {
            indeg[x]--;
            if (indeg[x] == 0)
                updateGraph(x, indeg, graph);
        }
    }

    vector<string> findAllRecipes(vector<string> &recipes, vector<vector<string>> &ingredients, vector<string> &supplies)
    {
        unordered_map<string, int> indeg;
        unordered_map<string, unordered_set<string>> graph;
        for (int i = 0; i < recipes.size(); i++)
        {
            indeg[recipes[i]] = ingredients[i].size();
            for (auto x : ingredients[i])
            {
                graph[x].insert(recipes[i]);
            }
        }

        for (auto x : supplies)
        {
            indeg[x] = 0;
            updateGraph(x, indeg, graph);
        }

        vector<string> ans;
        for (auto x : recipes)
        {
            if (indeg[x] == 0)
            {
                ans.push_back(x);
            }
        }
        return ans;
    }
};
// @lc code=end
